package com.tianyuan.test1;

/**动态规划*/
/**
 * 斐波那契数列
 *
 * @date 2025/10/21 16:00
 * 输入：4   返回值：3
 * 输入：1   返回值：1
 * 输入：2   返回值：1
 */
public class Solution {
    /**
     * 求解斐波那契数列的第n项
     * @param n 目标项的索引（从1开始计数）
     * @return 第n项的数值
     */
    public int Fibonacci (int n) {
        //  base case（递归终止条件）：
        //  当n为1或2时，斐波那契数列的第1项和第2项都是1
        if(n <= 2){
            return 1;
        }
        //  递归逻辑：第n项等于第n-1项加上第n-2项
        //  不断将问题拆解为更小的子问题（n-1和n-2），直到达到base case
        return Fibonacci(n-1) + Fibonacci(n-2);
    }







    public static void main(String[] args) {
        Solution solution = new Solution();
        // 测试用例1：输入4，预期返回3
        int n1 = 4;
        int result1 = solution.Fibonacci(n1);
        System.out.println("输入：" + n1 + " → 返回值：" + result1);
        // 测试用例2：输入1，预期返回1
        int n2 = 1;
        int result2 = solution.Fibonacci(n2);
        System.out.println("输入：" + n2 + " → 返回值：" + result2);
        // 测试用例3：输入2，预期返回1
        int n3 = 2;
        int result3 = solution.Fibonacci(n3);
        System.out.println("输入：" + n3 + " → 返回值：" + result3);
    }
}